package leetcode_201_220;

public class countPrimes_204 {
    /**
     * 传统方案
     * 超时
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        //小于非负整数 n 的质数的数量
        if (n<=2)   //n为2时，即只有0和1，质数个数为0
            return 0;
        int cnt=1;   //2 为质数
        for (int i=3;i< n;i++){
            if(isPrime(i)) cnt++;
        }
        return cnt;
    }
    public boolean isPrime(int n){
        for(int i=2;i * i <= n ; i++)  //根号n即可
            if(n%i==0) return false;
        return true;
    }

    /**
     * 用空间换时间
     */
    public int countPrimes2(int n) {
        int nums[]=new int[n];
        if (n<=2)   //n为2时，即只有0和1，质数个数为0
            return 0;
        int cnt=1;   //2 为质数
        for (int i = 2;  i * i < n ; i++) {
            if (nums[i] == 0) {              //只管素数即可，所有非质数都是质数的倍数
                for (int j = i * i ;  j < n ; j += i)
                        nums[ j ] = 1;
            }
        }
        for (int i = 3; i < n; i++)
            if (nums[i] == 0)
                cnt++;
        return cnt;
    }
}
